package dp;

/**
 * @author: june
 * @date: 2023/8/6
 * @description: 70. 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 动态规划
 **/

public class ClimbingStairs_70 {
    public int climbStairs(int n) {
        // 防止数组越界
        if (n == 1) {
            return 1;
        }
        // 1、确定dp数组，dp[i]表示爬到第i层有dp[i]种方法
        int[] dp = new int[n + 1];

        // 2、进行初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        // 3、递推公式推导，
        // 爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
        //那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
        //所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，
        // dp[i] = dp[i-1] + dp[i-2]
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
